package ljl.alg.wangzheng_camp.round1.bisection;

public class _10_05_find_string {
    
    /**
     * 我思路是找到空字符串后
     * 往左找第一个非空的，进行比较
     * 如果左边到头了，返回 “应该往右找”
     * <p>
     * 不应该左右都找，比较麻烦
     * <p>
     * 做对喽！
     * <p>
     * 我这个办法是不是笨了点，别人没人写我这么长的
     */
    int lastMet;
    
    public int findString_ben(String[] words, String s) {
        int l = 0, r = words.length - 1;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            String left = findLeft(words, mid);
            int cmp = left.compareTo(s);
            if (cmp == 0) return lastMet;
            if (cmp > 0) r = lastMet - 1;
            else {
                mid++;
                while (mid <= r && words[mid].equals("")) mid++;
                if (mid > r) break;
                l = mid;
            }
        }
        return -1;
    }
    
    String findLeft(String[] words, int i) {
        while (i >= 0 && words[i].equals("")) {
            i--;
        }
        if (i >= 0) {
            lastMet = i;
            return words[i];
        }
        return "\0";
    }
    
    /**
     * 还真有那么一点拐弯
     *
     * 找到 mid 后先往右找非空的串，如果全是空，直接退出？
     *      不能退出，得更新 r 为 mid - 1，“聪明的”
     * */
    public int findString(String[] words, String s) {
        int l = 0, r = words.length - 1;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            int old = mid;
            while (mid <= r && "".equals(words[mid])) mid++;
            if (mid > r) {
                r = old - 1;
                continue;
            }
            int cmp = words[mid].compareTo(s);
            if (cmp == 0) return mid;
            if (cmp < 0) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }
}
